#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<assert.h>

class ListNode
{
public:
    int val;
    ListNode* next;


};

    ListNode* CreateNode(int x)
    {
        ListNode* node = new ListNode;
        node->next = nullptr;
        node->val = x;
        return node;
    }

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* pcur1 = l1, * pcur2 = l2;
        Stack s1(pcur1), s2(pcur2);
        Stack a;
        while (!s1.IsEmpity() || !s2.IsEmpity())
        {
            if (!s1.IsEmpity() && !s2.IsEmpity())
            {
                int count = s1.Top() + s2.Top();
                s1.Pop();
                s2.Pop();
                if (count < 10)
                {
                    a.Push(count);
                }
                else
                {
                    a.Push(count % 10);
                    if (!s1.IsEmpity())
                        s1._a[s1._size]++;
                    else if (!s2.IsEmpity())
                        s2._a[s2._size]++;
                    else
                    {
                        a.Push(1);
                    }
                }

            }
            else if (!s1.IsEmpity() && s2.IsEmpity())
            {
                int count = s1.Top();
                s1.Pop();
                if (count < 10)
                {
                    a.Push(count);
                }
                else
                {
                    if (!s1.IsEmpity())
                        s1._a[s1._size]++;
                    else
                    {
                       
                        s1.Push(count / 10);
                    }
                    a.Push(count % 10);
                }

            }
            else
            {
                int count = s2.Top();
                s2.Pop();
                if (count < 10)
                {
                    a.Push(count);
                }
                else
                {
                    if (!s2.IsEmpity())
                        s2._a[s2._size]++;
                    else
                    {
                        
                        s2.Push(count / 10);
                    }
                    a.Push(count % 10);
                }

            }
        }
        ListNode* pcur = nullptr;
        while (!a.IsEmpity())
        {
            int count = a.Top();
            a.Pop();
            ListNode* node = CreateNode(count);
            if (ret == nullptr)
            {
                pcur = ret = node;
            }
            else
            {
                pcur->next = node;
                pcur = pcur->next;
            }

        }
        return ret;


    }

    ~Solution()
    {
        ListNode* del = ret;
        while (ret)
        {
            ret = ret->next;
            delete del;
            del = ret;
        }
    }

    typedef int TypeData;
    class Stack
    {
    public:

        Stack(ListNode* pcur)
            :_capacity(4)
            , _size(-1)
        {
            _a = (TypeData*)malloc(sizeof(TypeData) * 4);
            assert(_a);
            while (pcur)
            {
                Push(pcur->val);
                pcur = pcur->next;
            }
        }

        Stack()
            :_capacity(4)
            , _size(-1)
        {
            _a = (TypeData*)malloc(sizeof(TypeData) * 4);
            assert(_a);
        }

        TypeData Top()
        {
            assert(_size >= 0);
            return _a[_size];
        }

        void Pop()
        {
            assert(_size >= 0);
            _size--;
        }

        bool IsEmpity()
        {
            if (_size == -1)
                return 1;
            else
                return 0;
        }

        void Push(TypeData x)
        {
            if (_size + 1 >= _capacity)
            {
                int newcapacity = 2 * _capacity;
                TypeData* tmp = (TypeData*)realloc(_a, newcapacity * sizeof(TypeData));
                assert(tmp);
                _a = tmp;
                _capacity = newcapacity;
            }
            _a[++_size] = x;
        }



        ~Stack()
        {
            free(_a);
            _a = nullptr;
        }

        int GetSize()
        {
            return _size;
        }

        int GetAdd()
        {
            int sum = 0;
            for (int i = 0; i <= _size; i++)
            {
                sum += _a[i];
            }
            return sum;
        }


        int GetCapacity()
        {
            return _capacity;
        }

        TypeData* _a;
        int _size;
        int _capacity;
    };

    ListNode* ret = nullptr;
    
};

int main()
{
    
    ListNode n1;
    ListNode n2;
    ListNode n3;
    ListNode n4;
    ListNode n5;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = NULL;
    n4.next = &n5;
    n5.next = NULL;
    n1.val = 9;
    n2.val = 9;
    n3.val = 9;

    n4.val = 0;
    n5.val = 9;

    
    Solution s;
    ListNode* pcur = s.addTwoNumbers(&n2,&n5);
    while (pcur)
    {
        std::cout << pcur->val << "->";
        pcur = pcur->next;
    }
    return 0;
}